/*-
 * Copyright 2012 Guram Dukashvili
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
//---------------------------------------------------------------------------
#include "sys.h"
#include "str.h"
#include "idx.h"
//---------------------------------------------------------------------------
static void index_delete_key(
  struct index_link * link,
  uint32_t position,
  void * data)
{
  uintptr_t entry_size = link->idx->entries_sizes[link->blk.type];
  uint8_t * p = link->blk.keys + position * entry_size;

#if COMPILE_RUNTIME_CHECKS
  if( position >= link->blk.count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  if( link->blk.count > link->idx->blk_max_keys[link->blk.type] ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif

  if( link->blk.type == INDEX_LEAF ){
    if( data != NULL )
      memcpy(data,p + link->idx->key_size,link->idx->data_size);
  }
  else if( link->blk.type == INDEX_NODE ){
#if COMPILE_RUNTIME_CHECKS
    if( data != NULL ){
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
      abort();
    }
#endif
  }
#if COMPILE_RUNTIME_CHECKS
  else {
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif

  memcpy(p,p + entry_size,(link->blk.count - position - 1) * entry_size);

#if COMPILE_RUNTIME_CHECKS
  memset(p + (link->blk.count - 1) * entry_size,0,entry_size);
#endif

  link->blk.count--;
  link->serno++;
}
//---------------------------------------------------------------------------
void index_gather(
  struct index * idx,
  struct index_btree_stack * stack,
  const void * key,
  void * data)
{
  int err = ENOENT;
  intptr_t sp;
  struct index_btree_stack_entry * e, * t;
  enum RWLOCK_TYPE lock_type = RWL_WRITE;
  struct index * mvcc_idx;

  index_lookup(idx,stack,key,NULL,&mvcc_idx);

  if( errno == 0 ){
    index_get_key_path(mvcc_idx,stack,key,0);

    sp = stack->sp;
    e = array_get(&stack->entries,stack->sp);

    if( errno != 0 ){
      err = errno;
    }
    else if( e->c == 0 ){
      rwlock_acquire_write_lock(&mvcc_idx->readers_lock);

      rwlock_acquire_read_lock(&mvcc_idx->changed_links_lock);
      lock_type = RWL_UPGRADE;

      index_delete_key(e->link,e->position,data);
      e->link_change = ILC_UPD;

      while( sp > 0 ){
        uintptr_t half;
        
        t = array_get(&stack->entries,--sp);

        if( e->link_change != ILC_NONE && e->next_level_position == 0 ){
          memcpy(index_block_entry(t->link,t->next_level_position),e->link->blk.keys,mvcc_idx->key_size);
          t->link_change = ILC_UPD;
        }

        half = mvcc_idx->blk_max_keys[e->link->blk.type] / 2;

        if( e->link->blk.count == 0 ){
          index_delete_key(t->link,t->next_level_position,NULL); // delete link in top level
          // if delete last link from root then set root block type to leaf
          if( sp == 0 && t->link->blk.count == 0 )
            t->link->blk.type = INDEX_LEAF;
          t->link_change = ILC_UPD;
          e->link_change = ILC_DEL;
        }
        else if( e->link->blk.count < half ){
          // try to move all keys to top level block
          if( t->link->blk.type == e->link->blk.type
              && t->link->blk.count + e->link->blk.count - 1 <= mvcc_idx->node_max_key_count ){
            index_copy_paste_keys(t->link,t->next_level_position + 1,e->link,1,e->link->blk.count - 1);
            memcpy(index_block_entry(t->link,t->next_level_position) + mvcc_idx->key_size,
              e->link->blk.keys + mvcc_idx->key_size,mvcc_idx->block_index_size);
            t->link_change = ILC_UPD;
            e->link_change = ILC_DEL;
          }
          //else {
          //  uintptr_t space = e->left != NULL ? mvcc_idx->blk_max_keys[e->left->blk.type] - e->left->blk.count : 0;

          //  // try to distribute all keys to left neighbor
          //  if( e->link->blk.count <= space ){
          //    index_copy_paste_keys(e->left,e->left->blk.count,e->link,0,space);
          //    e->left_change = ILC_UPD;
          //    index_delete_key(t->link,t->next_level_position,NULL); // delete link in top level
          //    t->link_change = ILC_UPD;
          //    e->link_change = ILC_DEL;
          //  }
          //  else {
          //    uintptr_t overhalf;

          //    // try to distribute keys from left neighbor
          //    if( e->left != NULL ){
          //      half = mvcc_idx->blk_max_keys[e->left->blk.type] / 2;
          //      overhalf = e->left->blk.count - half;
          //      
          //      if( overhalf > 0 ){
          //        index_cut_paste_keys(e->link,0,e->left,half,overhalf);
          //        e->left_change = ILC_UPD;
          //        memcpy(index_block_entry(t->link,t->next_level_position),e->link->blk.keys,mvcc_idx->key_size);
          //        t->link_change = ILC_UPD;
          //        e->link_change = ILC_UPD;
          //      }
          //    }

          //    half = mvcc_idx->blk_max_keys[e->link->blk.type] / 2;
          //    if( e->link->blk.count < half ){ // and now what i may do?
          //      e = e;
          //    }
          //  }
          //}
        }
        e = t;
      }

      err = 0;

      rwlock_acquire(&mvcc_idx->changed_links_lock,lock_type);
      index_unwind_stack(mvcc_idx,stack,RWL_NONE);
      rwlock_release_write_lock(&mvcc_idx->changed_links_lock);

      rwlock_release_write_lock(&mvcc_idx->readers_lock);
    }
    if( idx != mvcc_idx ) index_put_mvcc(idx,mvcc_idx);
  }
  errno = err;
}
//---------------------------------------------------------------------------
